package leetcode

import com.sun.org.apache.xpath.internal.operations.Bool
import kotlinetc.println

//https://leetcode.com/problems/combination-sum/
fun main(args: Array<String>) {

    combinationSum(intArrayOf(2, 3, 6, 7), 7).println()
}


fun combinationSum(candidates: IntArray, target: Int): List<List<Int>> {

    val result = arrayListOf<List<Int>>()
    if (candidates.isEmpty()) return result
    //先排序，可以极大过滤掉不符合的情况
    candidates.sort()
//    val used = Array<Boolean>(candidates.size, { false })
    combinationSumRecursiveVersion1(candidates, 0, candidates[0], arrayListOf(), target, result)
    return result

}

/**
 * 没有去重重复
 */
fun combinationSumRecursive(candidates: IntArray, sum: Int, list: ArrayList<Int>, target: Int, result: ArrayList<List<Int>>) {


    for (i in 0 until candidates.size) {
        val r = candidates[i] + sum - target
        if (r == 0) {//不需要继续深度遍历，直接回到上一层
            list.add(candidates[i])
            result.add(ArrayList(list))
            list.removeAt(list.lastIndex)
            break
        } else if (r > 0) { //已经比target大，后续排列忽略
            //后续排列直接忽略
            break
        } else {
            list.add(candidates[i])

            combinationSumRecursive(candidates, sum + candidates[i], list, target, result)
            list.removeAt(list.lastIndex)

        }
    }
}


fun combinationSumRecursiveVersion1(candidates: IntArray, sum: Int, last: Int, list: ArrayList<Int>, target: Int, result: ArrayList<List<Int>>) {
    for (i in 0 until candidates.size) {
        if (candidates[i] < last) continue  //通过传排列中上一个数字，在下一层时候比较当前数字，强制只能往后寻找，这样去重
        val r = candidates[i] + sum - target
        if (r == 0) {//不需要继续深度遍历，直接回到上一层
            list.add(candidates[i])
            result.add(ArrayList(list))
            list.removeAt(list.lastIndex)
            break
        } else if (r > 0) { //已经比target大，后续排列忽略
            //后续排列直接忽略
            break
        } else {
            list.add(candidates[i])
            combinationSumRecursiveVersion1(candidates, sum + candidates[i], candidates[i], list, target, result)
            list.removeAt(list.lastIndex)
        }
    }
}